package com.yanceysong.codetop.s81_s90;

import java.util.HashMap;
import java.util.Map;

public class S90_Mid_560_和为K的子数组 {
    /**
     * .S90_Mid_560_和为K的子数组
     * .<p>
     * .<a href="https://leetcode.cn/problems/subarray-sum-equals-k/">...</a>
     * .<p>
     * .给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。
     * .<p>
     * .子数组是数组中元素的连续非空序列。
     * .<p>
     * .核心标签：数组、哈希表、前缀和
     * .<p>
     * .示例 1：
     * .<p>
     * .输入：nums = [1,1,1], k = 2
     * .输出：2
     * .解释：满足条件的子数组有：[1,1] 和 [1,1]（两个不同位置的子数组）
     * .<p>
     * .示例 2：
     * .<p>
     * .输入：nums = [1,2,3], k = 3
     * .输出：2
     * .解释：满足条件的子数组有：[1,2] 和 [3]
     * .<p>
     * .示例 3：
     * .<p>
     * .输入：nums = [1,-1,0], k = 0
     * .输出：3
     * .解释：满足条件的子数组有：[1,-1]、[-1,0] 和 [1,-1,0]
     * .<p>
     * .提示：
     * .<p>
     * .1 <= nums.length <= 2 * .10^4
     * .-1000 <= nums[i] <= 1000
     * .-10^7 <= k <= 10^7
     * .<p>
     * .解题思路：前缀和 + 哈希表
     * .<p>
     * .核心思想：
     * .1. 前缀和的定义：prefixSum[i] 表示从数组开始到索引 i 的所有元素之和
     * .2. 子数组 [i, j] 的和 = prefixSum[j] - prefixSum[i-1]
     * .3. 如果子数组 [i, j] 的和为 k，则：prefixSum[j] - prefixSum[i-1] = k
     * .4. 变换公式：prefixSum[i-1] = prefixSum[j] - k
     * .5. 因此，我们只需要在遍历过程中，查找之前是否存在前缀和为 (当前前缀和 - k) 的位置
     * .<p>
     * .关键洞察：
     * .- 使用哈希表存储每个前缀和出现的次数
     * .- 为什么存储次数而不是索引？因为可能有多个位置的前缀和相同，每个都能形成一个满足条件的子数组
     * .- 初始化：map.put(0, 1)，表示前缀和为 0 出现了 1 次（空数组的前缀和为 0）
     * .- 这样可以处理从数组开头就满足条件的子数组
     * .<p>
     * .算法步骤：
     * .1. 创建哈希表，key 为前缀和，value 为该前缀和出现的次数
     * .2. 初始化 map.put(0, 1)，表示前缀和为 0 出现 1 次
     * .3. 遍历数组，维护当前前缀和 currentSum
     * .4. 检查 map 中是否存在 (currentSum - k)，如果存在，说明找到了满足条件的子数组
     * .5. 将当前前缀和的出现次数加 1
     * .<p>
     * .图解示例 1：nums = [1, 1, 1], k = 2
     * .<p>
     * .索引：        0   1   2
     * .数组：       [1,  1,  1]
     * .前缀和：  0   1   2   3
     * .<p>
     * .遍历过程：
     * .<p>
     * .初始状态：
     * .map = {0: 1}  // 前缀和0出现1次
     * .count = 0
     * .currentSum = 0
     * .<p>
     * .步骤1：处理 nums[0] = 1
     * .currentSum = 0 + 1 = 1
     * .查找 map 中是否有 (1 - 2) = -1？ 没有
     * .count = 0
     * .更新 map = {0: 1, 1: 1}
     * .<p>
     * .步骤2：处理 nums[1] = 1
     * .currentSum = 1 + 1 = 2
     * .查找 map 中是否有 (2 - 2) = 0？ 有！出现了 1 次
     * .count = 0 + 1 = 1  // 找到子数组 [1,1]（索引0到1）
     * .更新 map = {0: 1, 1: 1, 2: 1}
     * .<p>
     * .步骤3：处理 nums[2] = 1
     * .currentSum = 2 + 1 = 3
     * .查找 map 中是否有 (3 - 2) = 1？ 有！出现了 1 次
     * .count = 1 + 1 = 2  // 找到子数组 [1,1]（索引1到2）
     * .更新 map = {0: 1, 1: 1, 2: 1, 3: 1}
     * .<p>
     * .最终结果：count = 2
     * .满足条件的子数组：
     * .- [1,1]（索引 0-1）：和为 2
     * .- [1,1]（索引 1-2）：和为 2
     * .<p>
     * .图解示例 2：nums = [1, 2, 3], k = 3
     * .<p>
     * .索引：        0   1   2
     * .数组：       [1,  2,  3]
     * .前缀和：  0   1   3   6
     * .<p>
     * .遍历过程：
     * .<p>
     * .初始：map = {0: 1}, count = 0, currentSum = 0
     * .<p>
     * .步骤1：nums[0] = 1
     * .currentSum = 1
     * .查找 (1 - 3) = -2？ 没有
     * .count = 0
     * .map = {0: 1, 1: 1}
     * .<p>
     * .步骤2：nums[1] = 2
     * .currentSum = 3
     * .查找 (3 - 3) = 0？ 有！出现 1 次
     * .count = 1  // 找到子数组 [1,2]（索引0到1）
     * .map = {0: 1, 1: 1, 3: 1}
     * .<p>
     * .步骤3：nums[2] = 3
     * .currentSum = 6
     * .查找 (6 - 3) = 3？ 有！出现 1 次
     * .count = 2  // 找到子数组 [3]（索引2）
     * .map = {0: 1, 1: 1, 3: 1, 6: 1}
     * .<p>
     * .最终结果：count = 2
     * .满足条件的子数组：
     * .- [1,2]（索引 0-1）：和为 3
     * .- [3]（索引 2）：和为 3
     * .<p>
     * .图解示例 3：nums = [1, -1, 0], k = 0
     * .<p>
     * .索引：        0   1   2
     * .数组：       [1, -1,  0]
     * .前缀和：  0   1   0   0
     * .<p>
     * .遍历过程：
     * .<p>
     * .初始：map = {0: 1}, count = 0, currentSum = 0
     * .<p>
     * .步骤1：nums[0] = 1
     * .currentSum = 1
     * .查找 (1 - 0) = 1？ 没有
     * .count = 0
     * .map = {0: 1, 1: 1}
     * .<p>
     * .步骤2：nums[1] = -1
     * .currentSum = 0
     * .查找 (0 - 0) = 0？ 有！出现 1 次
     * .count = 1  // 找到子数组 [1,-1]（索引0到1）
     * .map = {0: 2, 1: 1}  // 前缀和0现在出现2次
     * .<p>
     * .步骤3：nums[2] = 0
     * .currentSum = 0
     * .查找 (0 - 0) = 0？ 有！出现 2 次
     * .count = 1 + 2 = 3  // 找到子数组 [-1,0]（索引1到2）和 [1,-1,0]（索引0到2）
     * .map = {0: 3, 1: 1}
     * .<p>
     * .最终结果：count = 3
     * .满足条件的子数组：
     * .- [1,-1]（索引 0-1）：和为 0
     * .- [-1,0]（索引 1-2）：和为 0
     * .- [1,-1,0]（索引 0-2）：和为 0
     * .<p>
     * .为什么要初始化 map.put(0, 1)？
     * .- 考虑数组 [3], k = 3 的情况
     * .- 当遍历到 nums[0] = 3 时，currentSum = 3
     * .- 我们需要查找 (3 - 3) = 0 是否存在
     * .- 如果 map 中没有 0，就无法找到这个从头开始的子数组
     * .- 因此需要预先放入 (0, 1)，表示"空数组"的前缀和为 0
     * .<p>
     * .时间复杂度：O(n)，其中 n 是数组长度
     * .- 只需要遍历数组一次
     * .- 哈希表的插入和查询操作都是 O(1)
     * .<p>
     * .空间复杂度：O(n)
     * .- 最坏情况下，哈希表需要存储 n 个不同的前缀和
     * .- 例如数组 [1, 2, 3, 4, 5]，每个前缀和都不同
     */
    public int subarraySum(int[] nums, int k) {
        // 哈希表：key 为前缀和，value 为该前缀和出现的次数
        Map<Integer, Integer> prefixSumCount = new HashMap<>();
        
        // 初始化：前缀和为 0 出现 1 次（表示空数组的前缀和）
        // 这样可以处理从数组开头就满足条件的子数组
        prefixSumCount.put(0, 1);
        
        // 记录满足条件的子数组个数
        int count = 0;
        
        // 当前的前缀和
        int currentSum = 0;
        
        // 遍历数组中的每个元素
        for (int num : nums) {
            // 更新当前前缀和
            currentSum += num;
            
            // 检查是否存在前缀和为 (currentSum - k) 的位置
            // 如果存在，说明从那个位置到当前位置的子数组和为 k
            // 有多少个这样的位置，就有多少个满足条件的子数组
            if (prefixSumCount.containsKey(currentSum - k)) {
                count += prefixSumCount.get(currentSum - k);
            }
            
            // 将当前前缀和的出现次数加 1
            // 使用 getOrDefault 处理首次出现的情况
            prefixSumCount.put(currentSum, prefixSumCount.getOrDefault(currentSum, 0) + 1);
        }
        
        return count;
    }

    public static void main(String[] args) {
        S90_Mid_560_和为K的子数组 solution = new S90_Mid_560_和为K的子数组();

        System.out.println("=== 和为K的子数组测试开始 ===");

        // 测试1: 示例1 - [1,1,1], k=2
        System.out.println("\n--- 测试1: 示例1 [1,1,1], k=2 ---");
        testCase1(solution);

        // 测试2: 示例2 - [1,2,3], k=3
        System.out.println("\n--- 测试2: 示例2 [1,2,3], k=3 ---");
        testCase2(solution);

        // 测试3: 示例3 - [1,-1,0], k=0
        System.out.println("\n--- 测试3: 示例3 [1,-1,0], k=0 ---");
        testCase3(solution);

        // 测试4: 单个元素，匹配
        System.out.println("\n--- 测试4: 单个元素 [5], k=5 ---");
        testCase4(solution);

        // 测试5: 单个元素，不匹配
        System.out.println("\n--- 测试5: 单个元素 [5], k=3 ---");
        testCase5(solution);

        // 测试6: 全部元素和等于k
        System.out.println("\n--- 测试6: [1,2,3,4], k=10 ---");
        testCase6(solution);

        // 测试7: 包含负数
        System.out.println("\n--- 测试7: [3,4,7,2,-3,1,4,2], k=7 ---");
        testCase7(solution);

        // 测试8: 所有元素都为0
        System.out.println("\n--- 测试8: [0,0,0], k=0 ---");
        testCase8(solution);

        // 测试9: 没有满足条件的子数组
        System.out.println("\n--- 测试9: [1,2,3], k=10 ---");
        testCase9(solution);

        // 测试10: 多个相同前缀和
        System.out.println("\n--- 测试10: [1,-1,1,-1], k=0 ---");
        testCase10(solution);

        System.out.println("\n=== 所有测试完成 ===");
    }

    /**
     * .测试1: 示例1
     * .nums = [1,1,1], k = 2
     * .满足条件的子数组：[1,1]（索引0-1）、[1,1]（索引1-2）
     */
    private static void testCase1(S90_Mid_560_和为K的子数组 solution) {
        int[] nums = {1, 1, 1};
        int k = 2;
        System.out.println("数组: [1,1,1]");
        System.out.println("目标和 k: " + k);
        int result = solution.subarraySum(nums, k);
        System.out.println("subarraySum() -> " + result + " (期望: 2)");
        System.out.println("满足条件的子数组: [1,1]（索引0-1）、[1,1]（索引1-2）");
        assert result == 2 : "应该找到2个子数组";
        System.out.println("✓ 测试1通过");
    }

    /**
     * .测试2: 示例2
     * .nums = [1,2,3], k = 3
     * .满足条件的子数组：[1,2]、[3]
     */
    private static void testCase2(S90_Mid_560_和为K的子数组 solution) {
        int[] nums = {1, 2, 3};
        int k = 3;
        System.out.println("数组: [1,2,3]");
        System.out.println("目标和 k: " + k);
        int result = solution.subarraySum(nums, k);
        System.out.println("subarraySum() -> " + result + " (期望: 2)");
        System.out.println("满足条件的子数组: [1,2]（索引0-1）、[3]（索引2）");
        assert result == 2 : "应该找到2个子数组";
        System.out.println("✓ 测试2通过");
    }

    /**
     * .测试3: 示例3
     * .nums = [1,-1,0], k = 0
     * .满足条件的子数组：[1,-1]、[-1,0]、[1,-1,0]
     */
    private static void testCase3(S90_Mid_560_和为K的子数组 solution) {
        int[] nums = {1, -1, 0};
        int k = 0;
        System.out.println("数组: [1,-1,0]");
        System.out.println("目标和 k: " + k);
        int result = solution.subarraySum(nums, k);
        System.out.println("subarraySum() -> " + result + " (期望: 3)");
        System.out.println("满足条件的子数组: [1,-1]、[-1,0]、[1,-1,0]");
        assert result == 3 : "应该找到3个子数组";
        System.out.println("✓ 测试3通过");
    }

    /**
     * .测试4: 单个元素，匹配
     * .nums = [5], k = 5
     */
    private static void testCase4(S90_Mid_560_和为K的子数组 solution) {
        int[] nums = {5};
        int k = 5;
        System.out.println("数组: [5]");
        System.out.println("目标和 k: " + k);
        int result = solution.subarraySum(nums, k);
        System.out.println("subarraySum() -> " + result + " (期望: 1)");
        System.out.println("满足条件的子数组: [5]");
        assert result == 1 : "应该找到1个子数组";
        System.out.println("✓ 测试4通过");
    }

    /**
     * .测试5: 单个元素，不匹配
     * .nums = [5], k = 3
     */
    private static void testCase5(S90_Mid_560_和为K的子数组 solution) {
        int[] nums = {5};
        int k = 3;
        System.out.println("数组: [5]");
        System.out.println("目标和 k: " + k);
        int result = solution.subarraySum(nums, k);
        System.out.println("subarraySum() -> " + result + " (期望: 0)");
        System.out.println("没有满足条件的子数组");
        assert result == 0 : "不应该找到子数组";
        System.out.println("✓ 测试5通过");
    }

    /**
     * .测试6: 全部元素和等于k
     * .nums = [1,2,3,4], k = 10
     * .满足条件的子数组：[1,2,3,4]
     */
    private static void testCase6(S90_Mid_560_和为K的子数组 solution) {
        int[] nums = {1, 2, 3, 4};
        int k = 10;
        System.out.println("数组: [1,2,3,4]");
        System.out.println("目标和 k: " + k);
        int result = solution.subarraySum(nums, k);
        System.out.println("subarraySum() -> " + result + " (期望: 1)");
        System.out.println("满足条件的子数组: [1,2,3,4]");
        assert result == 1 : "应该找到1个子数组";
        System.out.println("✓ 测试6通过");
    }

    /**
     * .测试7: 包含负数的复杂情况
     * .nums = [3,4,7,2,-3,1,4,2], k = 7
     * .满足条件的子数组：[3,4]、[7]、[7,2,-3,1]、[2,-3,1,4,2]、[-3,1,4,2]
     */
    private static void testCase7(S90_Mid_560_和为K的子数组 solution) {
        int[] nums = {3, 4, 7, 2, -3, 1, 4, 2};
        int k = 7;
        System.out.println("数组: [3,4,7,2,-3,1,4,2]");
        System.out.println("目标和 k: " + k);
        int result = solution.subarraySum(nums, k);
        System.out.println("subarraySum() -> " + result + " (期望: 4)");
        System.out.println("满足条件的子数组: [3,4]、[7]、[7,2,-3,1]、[2,-3,1,4,2]");
        assert result == 4 : "应该找到4个子数组";
        System.out.println("✓ 测试7通过");
    }

    /**
     * .测试8: 所有元素都为0
     * .nums = [0,0,0], k = 0
     * .满足条件的子数组：[0]（3个）、[0,0]（2个）、[0,0,0]（1个）= 6个
     */
    private static void testCase8(S90_Mid_560_和为K的子数组 solution) {
        int[] nums = {0, 0, 0};
        int k = 0;
        System.out.println("数组: [0,0,0]");
        System.out.println("目标和 k: " + k);
        int result = solution.subarraySum(nums, k);
        System.out.println("subarraySum() -> " + result + " (期望: 6)");
        System.out.println("满足条件的子数组: [0]×3 + [0,0]×2 + [0,0,0]×1 = 6个");
        assert result == 6 : "应该找到6个子数组";
        System.out.println("✓ 测试8通过");
    }

    /**
     * .测试9: 没有满足条件的子数组
     * .nums = [1,2,3], k = 10
     */
    private static void testCase9(S90_Mid_560_和为K的子数组 solution) {
        int[] nums = {1, 2, 3};
        int k = 10;
        System.out.println("数组: [1,2,3]");
        System.out.println("目标和 k: " + k);
        int result = solution.subarraySum(nums, k);
        System.out.println("subarraySum() -> " + result + " (期望: 0)");
        System.out.println("没有满足条件的子数组");
        assert result == 0 : "不应该找到子数组";
        System.out.println("✓ 测试9通过");
    }

    /**
     * .测试10: 多个相同前缀和
     * .nums = [1,-1,1,-1], k = 0
     * .满足条件的子数组：[1,-1]（2个）、[1,-1,1,-1]、[-1,1]
     */
    private static void testCase10(S90_Mid_560_和为K的子数组 solution) {
        int[] nums = {1, -1, 1, -1};
        int k = 0;
        System.out.println("数组: [1,-1,1,-1]");
        System.out.println("目标和 k: " + k);
        int result = solution.subarraySum(nums, k);
        System.out.println("subarraySum() -> " + result + " (期望: 4)");
        System.out.println("满足条件的子数组: [1,-1]×2 + [1,-1,1,-1] + [-1,1] = 4个");
        assert result == 4 : "应该找到4个子数组";
        System.out.println("✓ 测试10通过");
    }
}

